package main

import (
	"fmt"
	"math/rand"
	"time"
)

// var color = []string{"nil", "red", "yellow", "green", "blue", "purple", "white", "black", "pink"}

func translate(A [][]byte) {
	fmt.Printf("[")
	for _, v := range A {
		for _, vv := range v {
			fmt.Printf("%d ", vv)
		}
		fmt.Printf("\n")
	}
	fmt.Printf("]\n")
}

func main() {
	A := RandGraph(50, 50)
	fmt.Println("随机")
	//DisplayA(A)
	translate(A)

	n := len(A)
	for i := 0; i < n-1; i++ {
		for j := i + 1; j < n; j++ {
			A[j][i] = A[i][j]
		}
	}
	fmt.Println("对称")
	DisplayA(A)

	//找最大度、最小度
	//对于任意图 k <= max + 1
	//k <= max2 + 1
	//Chaitin1(A)

	// fmt.Println("溢出数量", Chaitin2(A, 0))

	// testspillchaitin()

	// q := BriggsSimply(A)
	// node, s := BriggsSelect(A, q, 8)
	// fmt.Println(node)
	// for i := 0; i < len(node); i++ {
	// 	fmt.Printf("%d ", node[i])
	// }
	// fmt.Println()
	// fmt.Println(s)
	// Check(A, node)

	//findbound()
	//ctime()
	testspillbriggs()
}

func Briggs(A [][]byte) {
	q := BriggsSimply(A)
	node, s := BriggsSelect(A, q, 8)
	// fmt.Println(node)
	for i := 0; i < len(node); i++ {
		fmt.Printf("%d ", node[i])
	}
	fmt.Println()
	fmt.Println(s)
	Check(A, node)
}

//根据参数生成随机矩阵， n是节点个数， p是节点连接概率
func RandGraph(n int, p int) (A [][]byte) {
	//创建矩阵
	A = make([][]byte, n)
	for i := 0; i < n; i++ {
		A[i] = make([]byte, n)
	}

	rand.Seed(time.Now().UnixNano())
	for {
		//生成随机矩阵
		for i := 0; i < n-1; i++ {
			for j := i + 1; j < n; j++ {
				prob := rand.Intn(100)
				if p > prob {
					A[i][j] = 1
				} else {
					A[i][j] = 0
				}
			}
		}
		//fmt.Println("尝试")
		//DisplayA(A)
		if Justice(A) {
			break
		}
		//fmt.Println("失败")
	}
	//初始化矩阵
	return A
}

//BFS判断连通性
func Justice(A [][]byte) (flag bool) {
	var q Queue
	q.initQueue()
	flag = false

	//记录遍历过的节点
	map_node := make(map[int]bool)
	for i := 0; i < len(A); i++ {
		map_node[i] = false
	}
	map_node[0] = true

	//入队
	for i := 1; i < len(A); i++ {
		if A[0][i] == 1 {
			q.Enqueue(i)
			map_node[i] = true
			flag = true
		}
	}

	if !flag {
		//fmt.Println("节点0未连接")
		return false
	}

	// 开始bfs
	for {
		nn := q.Dequeue()
		n := (*nn).(int)
		for i := n + 1; i < len(A); i++ {
			if A[n][i] == 1 {
				if !map_node[i] {
					q.Enqueue(i)
					map_node[i] = true
				}
			}
		}

		//检验是否全部遍历到
		flag = true
		for _, v := range map_node {
			if !v {
				flag = false
			}
		}
		if flag {
			return true
		}
		if q.IsEmpty() {
			//fmt.Println(map_node)
			break
		}
	}
	return flag
}

//打印矩阵
func DisplayA(A [][]byte) {
	for _, v := range A {
		fmt.Println(v)
	}
}

func Check(A [][]byte, node map[int]int) {
	n := len(A)
	for i := 0; i < n; i++ {
		a := node[i]
		if a != 0 {
			for j := 0; j < n; j++ {
				if i != j {
					if A[i][j] == 1 {
						if node[j] == a {
							fmt.Println("error", i, j)
							return
						}

					}
				}
			}
		}
	}
	fmt.Println("success")
}

//chaitin算法方案一-不断增加颜色个数直到找到解
func Chaitin1(A [][]byte) {
	d := CalculateD(A)
	max, _ := Max(d)
	min, l := Min(d)
	// TODO: min有问题，忘记是啥了
	min = 0 //
	fmt.Println("最小度位置", l)
	for i := min + 1; i <= max+1; i++ {
		fmt.Println("尝试", i)
		// DisplayA(A)
		f, q := ChaitinSimply(A, i)
		if f {
			fmt.Println("可", i, "着色")
			fmt.Println(q)
			node := ChaitinSelect(A, q, i)
			//fmt.Println(node)
			// for k, v := range node {
			//fmt.Println("节点", k, color[v])
			// }
			for i := 0; i < len(node); i++ {
				fmt.Printf("%d ", node[i])
			}
			Check(A, node)
			break
		} else {
			fmt.Println("不可", i, "着色")
		}
	}
}

//chaitin算法方案二-到达指定数量后开始溢出 k是迭代用的，指定数量请改i<=8
func Chaitin2(A [][]byte, k int) (spill int) {
	for i := 2; i <= 8; i++ {
		// fmt.Println("尝试", i)
		//DisplayA(A)
		f, q := ChaitinSimply(A, i)
		if f {
			fmt.Println("可", i, "着色")
			fmt.Println(q)
			node := ChaitinSelect(A, q, i)
			//fmt.Println(node)
			// for k, v := range node {
			//fmt.Println("节点", k, color[v])
			// }
			for i := 0; i < len(node); i++ {
				fmt.Printf("%d ", node[i])
			}
			Check(A, node)
			return k
		} else {
			// fmt.Println("不可", i, "着色")
		}
	}
	fmt.Println("开始溢出")
	for {
		n := len(A) - 1
		Aa := make([][]byte, n) //go语言中切片是地址
		for i := 0; i < n; i++ {
			Aa[i] = make([]byte, n)
		}
		for i := 0; i < n; i++ {
			for j := 0; j < n; j++ {
				Aa[i][j] = A[i+1][j+1]
			}
		}
		return Chaitin2(Aa, k+1)
	}
}

//chaitin算法-化简部分 输入邻接矩阵、颜色个数，返回是否能染色，节点队列
func ChaitinSimply(Aa [][]byte, k int) (bool, Queue) {
	n := len(Aa)

	a := make([]int, n)
	var q Queue
	q.initQueue()
	//fmt.Println(q)

	A := make([][]byte, n) //go语言中切片是地址
	for i := 0; i < n; i++ {
		A[i] = make([]byte, n)
	}
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			A[i][j] = Aa[i][j]
		}
	}

	//循环开始
	for { //i := 0; i < n; i++ {

		d := CalculateD(A)
		min, location := Min(d)
		if min < k || min == 100000 { //存在一个节点度小于k
			if location == -1 { //整个图都被移除
				for k, v := range a {
					if v == 0 {
						// fmt.Println("移除节点", k) //最后有个节点没加进去
						q.Enqueue(k)
					}
				}
				return true, q
			} else { //移除该节点
				for j := 0; j < n; j++ {
					A[location][j] = 0
					A[j][location] = 0
				}
				q.Enqueue(location)
				a[location] = 1
				// fmt.Println("移除节点", location)
				// fmt.Println(q)
				// DisplayA(A)
			}
		} else { //不存在一个节点度小于k
			return false, q
		}
	}
}

//chaitin算法-着色部分 输入邻接矩阵、节点队列、颜色个数，返回染色结构
func ChaitinSelect(A [][]byte, q Queue, k int) (node map[int]int) {
	node = make(map[int]int)
	for i := 0; i < q.Size(); i++ {
		node[i] = 0
	}

	//fmt.Println("开始染色", k)
	// DisplayA(A)
	for {
		nn := q.Dequeue()
		n := (*nn).(int)
		//fmt.Println("对", n, "进行着色")
		color := make([]int, k+1)
		for i := 0; i < len(A); i++ { //检查相邻节点是否着色
			if A[n][i] != 0 {
				// fmt.Println("相邻节点", i)
				if node[i] != 0 {
					// fmt.Println("已着色", node[i])
					color[node[i]] = 1
				}
			}
		}
		// fmt.Println(A[n])
		// fmt.Println(node)
		// fmt.Println(color)
		// fmt.Println()
		for i := 1; i < k+1; i++ {
			if color[i] == 0 { //发现未使用颜色
				node[n] = i
				break
			}
		}
		if q.IsEmpty() {
			break
		}
	}

	return node
}

func BriggsSimply(Aa [][]byte) Queue {
	n := len(Aa)

	var q Queue
	q.initQueue()
	//fmt.Println(q)

	A := make([][]byte, n) //go语言中切片是地址
	for i := 0; i < n; i++ {
		A[i] = make([]byte, n)
	}
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			A[i][j] = Aa[i][j]
		}
	}

	//循环开始
	for i := 0; i < n-1; i++ {
		d := CalculateD(A)
		_, location := Min(d)
		//移除该节点
		for j := 0; j < n; j++ {
			A[location][j] = 0
			A[j][location] = 0
		}
		q.Enqueue(location)
	}
	return q
}

func BriggsSelect(A [][]byte, q Queue, k int) (node map[int]int, spill int) {
	node = make(map[int]int)
	for i := 0; i < q.Size(); i++ {
		node[i] = 0
	}

	for {
		nn := q.Dequeue()
		n := (*nn).(int)
		//fmt.Println("对", n, "进行着色")
		color := make([]int, k+1)
		var f int
		for i := 0; i < len(A); i++ { //检查相邻节点是否着色
			if A[n][i] != 0 {
				// fmt.Println("相邻节点", i)
				if node[i] != 0 {
					// fmt.Println("已着色", node[i])
					color[node[i]] = 1
				}
			}

		}
		for i := 1; i < k+1; i++ {
			if color[i] == 0 { //发现未使用颜色
				node[n] = i
				f = 1
				break
			}
		}
		if f == 0 {
			fmt.Println("溢出节点", n)
			spill = spill + 1
		}
		if q.IsEmpty() {
			break
		}
	}

	return node, spill
}

//计算节点度
func CalculateD(A [][]byte) (d []int) {
	n := len(A)
	d = make([]int, n)
	for i := 0; i < n; i++ {
		d[i] = 0
		for j := 0; j < n; j++ {
			d[i] = d[i] + int(A[i][j])
		}
	}
	return d
}

func Max(d []int) (max int, location int) {
	max = -1
	location = -1
	for i := 0; i < len(d); i++ {
		if d[i] > max {
			max = d[i]
			location = i
		}
	}
	return max, location
}

func Min(d []int) (min int, location int) {
	min = 100000
	location = -1
	for i := 0; i < len(d); i++ {
		if d[i] > 0 {
			if d[i] < min {
				min = d[i]
				location = i
			}
		}
	}

	return min, location
}
